package CodingTest;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
/**
 * 输入一个字符串,按字典序打印出该字符串中字符的所有排列。
 * 例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab
 * 和cba。**/
public class Solution {
    static class TreeNode{
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
        public TreeNode(int val){
            this.val = val;
        }
    }

        public ArrayList<String> Permutation(String str){
        List<String> res = new ArrayList<>();
        if(str != null && str.length()>0){
            PermutationHelper(str.toCharArray(),0,res);
            Collections.sort(res);
        }
        return (ArrayList)res;
        }
        //i为cs字符串交换的头字符
        public void PermutationHelper(char[] cs,int i,List<String> list ){
        if(i == cs.length - 1 ){
            String val = String.valueOf(cs);
            if(!list.contains(val))
                list.add(val);
        }
        else{
            for(int j = i;j < cs.length;j++){
                swap(cs,i,j);
                PermutationHelper(cs,i+1,list);
                //此处增加一个swap（）函数旨在将已经交换的字符串还原，如abc在交换ab之后为bac，
                //再使用一次swap（），则将还原为abc以便下次交换
                swap(cs,i,j);
            }
        }
        }
        //交换字符函数
        public void swap(char[] cs,int i,int j){
        char temp = cs[i];
        cs[i] = cs[j];
        cs[j] = temp;
        }
}




